/**
 * #### 数组反转
 * @param arr 数组
 */
export function reverse(arr: string[]) {
  let l = -1,
    r = arr.length;
  while (++l < --r) {
    [arr[l], arr[r]] = [arr[r], arr[l]];
  }
}

/**
 * #### 两数之和
 * @description
 * 1、暴力法，时间复杂度O(n^2)；
 * 2、排序+双指针，时间复杂度O(nlogn)；
 * 3、哈希表，时间复杂度O(n)；
 * @param nums 数组
 * @param target 目标值
 * @returns
 */
export function twoSum(nums: number[], target: number) {
  const map = new Map();
  for (let i = 0, len = nums.length; i < len; i++) {
    const diff = target - nums[i];
    if (map.has(diff)) {
      return [map.get(diff), i];
    }
    map.set(nums[i], i);
  }
  return [];
}

// 导出一个函数，用于找到矩阵的对角线顺序
export function findDiagonalOrder(matrix: number[][]) {
  // 定义一个空数组，用于存储结果
  const res: number[] = [];
  // 获取矩阵的行数和列数
  const row = matrix.length,
    col = matrix[0].length;
  // 遍历矩阵的行数和列数之和减一
  for (let i = 0; i < row + col - 1; i++) {
    // 如果i是偶数
    if (i % 2 == 0) {
      // 定义x和y的初始值
      let x = i < row ? i : row - 1;
      let y = i < row ? 0 : i - row + 1;
      // 当x大于等于0且y小于列数时，将矩阵中的元素添加到结果数组中，并更新x和y的值
      while (x >= 0 && y < col) {
        res.push(matrix[x--][y++]);
      }
    } else {
      // 如果i是奇数
      // 定义x和y的初始值
      let x = i < col ? 0 : i - col + 1;
      let y = i < col ? i : col - 1;
      // 当y大于等于0且x小于行数时，将矩阵中的元素添加到结果数组中，并更新x和y的值
      while (y >= 0 && x < row) {
        res.push(matrix[x++][y--]);
      }
    }
  }
  // 返回结果数组
  return res;
}

/**
 * #### 最长递增子序列
 * @author duyi
 * @see https://www.bilibili.com/video/BV1jUPyeXEkK?spm_id_from=333.788.videopod.sections&vd_source=9efadbd9bd76b9c14f9589f260a0c1ac
 * @param nums 数值数组
 * @returns
 * @example
 * ``` ts
 * LIS([10, 9, 2, 5, 3, 7, 101, 18]) // [2, 3, 7, 101]
 * ```
 */
export function LIS(nums: number[]) {
  if (!nums.length) return [];
  const result = [[nums[0]]];
  for (let i = 1; i < nums.length; i++) {
    const cur = nums[i];
    _update(cur);
  }
  function _update(n: number) {
    for (let i = result.length - 1; i >= 0; i--) {
      const line = result[i];
      const last = line[result[i].length - 1];
      if (last < n) {
        result[i + 1] = [...line, n];
        break;
      } else if (last > n && i === 0) {
        result[i] = [n];
      }
    }
  }
  return result[result.length - 1];
}
